1629 곱셈
나머지 지수승 관련한 이산수학 교재 캡처 추가. 이 알고리즘이 기반한 원리는 x
일지 몰라도 그 x에 붙일 계수를 알기 위해선 당연하게도 power
를 지수승만큼 증가시켜야 한다. 그런데 그냥 power
를 매 이터레이션마다 제곱을 시키는 것이다.
아래 교재의 예시인 x = (x * power) mod m
을 구하고, power는 매 이터레이션마다
source code
"""modular exponentiation 참고: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation"""
from math import ceil, log2
def modular_exponentiation(b: int, exp: int, m: int):
"""나머지 지수승 연산을 수행하는 알고리즘.
$
b^{exp} \mod m
$
"""
x = 1
power = b % m
k = ceil(log2(exp)) + 1 # e의 이진전개의 길이, 1을 더하는 이유는 예외처리 때문이다. 2의 지수승을 e에 넣어보고 풀면 결과가 이상하다. 왜냐하면 아래 for문의 if문을 하나도 통과하지 않기 때문이지.
for i in range(k):
if (exp >> i) & 1 == 1:
# a_i = 1 then,
x = (x * power) % m
power = (power * power) % m
return x
b, exp, m = [int(x) for x in input().split()]
print(modular_exponentiation(b, exp, m))